package com.some;

public class XiaPi_3 {
    /**
     * Note: 类名、方法名、参数名已经指定，请勿修改
     *
     * @param n int整型
     * @return int整型
     */
    int ans = 0;

    public int buildHouses(int n) {
        // write code here
        dfs(n, 0, 0, 0, 0);
        return ans;
    }

    private void dfs(int n, int row, int cols, int pie, int na) {
        if (row == n) {
            this.ans++;
            return;
        }
        int positions = ((1 << n) - 1) & (~(cols | pie | na));
        while (positions != 0) {
            int p = positions & (-positions);
            positions &= (positions - 1);
            dfs(n, row + 1, cols | p, (pie | p) << 1, (na | p) >> 1);
        }
    }
}
